#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
private:
    void traversal(TreeNode *node, string path, vector<string> &res)
    {
        path += to_string(node->val);
        if (node->left == nullptr && node->right == nullptr) {
            res.push_back(path);
            return;
        }

        if (node->left) traversal(node->left, path + "->", res);
        if (node->right) traversal(node->right, path + "->", res);
    }
public:
    vector<string> binaryTreePaths(TreeNode *root)
    {
        // 1.递归法
        // vector<string> res;
        // string path;
        // if (root == nullptr) return res;
        // traversal(root, path, res);
        // return res;

        // 2. 迭代法
        vector<string> res;
        stack<TreeNode *> treeSt;
        stack<string> pathSt;
        if(root == nullptr) return res; 
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while(!treeSt.empty()){
            TreeNode * node = treeSt.top();
            treeSt.pop();
            string path = pathSt.top();
            pathSt.pop();
            if(node->left == nullptr && node->right == nullptr){
                res.push_back(path);
            }

            if(node->right){ //右
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }

            if(node->left){ //左
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
            
        }
        return res;
    }
};